#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
//打印链表元素
void SLTPrint(SLTNode* phead)
{
	SLTNode* ptmp = phead;
	while (ptmp)
	{
		printf("%d->", ptmp->data);
		ptmp = ptmp->next;
	}
	printf("NULL\n");
}
//申请新链表节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* pnew = (SLTNode*)malloc(sizeof(SLTNode));
	if (pnew == NULL)
	{
		perror("申请节点失败");
		exit(1);
	}
	pnew->data = x;
	pnew->next = NULL;
	return pnew;
}
//寻找链表尾端的前一个结点
SLTNode** FindTailFront(SLTNode** pphead)
{
	//因为这个函数肯定是在别的函数里被引用的，能进行到这里pphead肯定不为空，就没加断言
	while ((*pphead)->next->next)
	{
		pphead = &((*pphead)->next);
	}
	return pphead;
}
//尾部插入
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pnew = SLTBuyNode(x);
	if (*pphead && (*pphead)->next)//非单节点链表，需要找尾
	{
		pphead = FindTailFront(pphead);
		(*pphead)->next->next = pnew;
	}
	else if (*pphead == NULL)//空链表，直接赋值
	{
		(*pphead) = pnew;
	}
	else//单节点链表，给next赋值
	{
		(*pphead)->next = pnew;
	}
}
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
	while (*pphead)//空链表根本不会进循环，函数不起任何作用，所以断言的时候就不把*pphead也丢进去，判断它是不是空链表了
	{
		assert(pphead);
		SLTNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}
void CommonSet(SLTNode* phead1, SLTNode* phead2, SLTNode** pphead1)//写完后仔细读了题干后感觉可能应该直接改变phead1才对
//所以应该不需要传phead1本身。可是主体已经不想改了，就这样吧
{
	SLTNode* pcur1 = phead1;
	SLTNode* pcur2 = phead2;
	SLTNode* ret = NULL;
	SLTNode* pcur3 = NULL;
	int flag = 1;
	if (phead1 && phead2)//如果有任何一方是空链表，接下来的操作都不用做，将链表1变为空即可
	{

		while (pcur1->next && pcur2->next)
		{
			if (pcur1->data != pcur2->data)
			{
				if (pcur1->data > pcur2->data)
				{
					pcur2 = pcur2->next;
				}
				else
				{
					pcur1 = pcur1->next;
				}
			}
			else
			{
				if (flag)//找到了两链表第一个开始匹配的节点，
				{
					ret = pcur1;
					pcur3 = pcur1;
					flag = 0;
				}
				else
				{
					pcur3->next = pcur1;
					pcur3 = pcur3->next;
				}
				pcur1 = pcur1->next;
				pcur2 = pcur2->next;
			}
		}
		//无论哪一方因为只有一个节点而跳出循环，接下来只需要让二者下个节点的值相互比较，判断是否保留即可
		if (pcur2->data == pcur1->data)
		{
			if (flag)//如果先前所有节点交集为空集，返回这唯一一个节点就好，否则返回此时仍为NULL的ret
			{
				ret = pcur1;
			}
		}
	}
	*pphead1 = ret;
}
//同理，第四题要把函数换成这个
int CommonSet(SLTNode* phead1, SLTNode* phead2, SLTNode** pphead1)
//{
//	SLTNode* pcur1 = phead1;
//	SLTNode* pcur2 = phead2;
//	SLTNode* ret = NULL;
//	SLTNode* pcur3 = NULL;
//	int flag = 1;
//  int count=0;
//	if (phead1 && phead2)//如果有任何一方是空链表，接下来的操作都不用做
//	{
//
//		while (pcur1->next && pcur2->next)
//		{
//			if (pcur1->data != pcur2->data)
//			{
//				if (flag)//找到了两链表第一个开始不同的节点，
//				{
//					ret = pcur1;
//					pcur3 = pcur1;
//					flag = 0;
//                  count++;
//				}
//				else if (pcur3->data != pcur1->data)//防止出现重复元素和死循环
//				{
//					pcur3->next = pcur1;
//					pcur3 = pcur3->next;
//                  count++;
//				}
//				if (pcur1->data < pcur2->data)
//				{
//					pcur1 = pcur1->next;
//				}
//				else
//				{
//					pcur2 = pcur2->next;
//				}
//			}
//			else
//			{
//				pcur1 = pcur1->next;
//				pcur2 = pcur2->next;
//			}
//		}
//		//无论哪一方因为只有一个节点而跳出循环，接下来只需要让二者下个节点的值相互比较，判断是否保留即可
//		if (pcur2->data != pcur1->data)
//		{
//			if (flag)//如果先前所有节点差集为空集，返回这唯一一个节点就好，否则返回此时仍为NULL的ret
//			{
//				ret = pcur1;
//			}
//			else
//			{
//				pcur3->next = pcur1;
//				pcur3 = pcur3->next;
//			}
//			count++;
//		}
//		//此时可能还会出现pcur3后的所有节点都不应留的情况（因为尾插的时候不只是插入了一个节点，还包括这之后的所有节点）
//		//所以需要将其后的尾端置空。对于其余条件，这样虽然多余，却不会产生坏影响，所以保留
//		if(flag==0)
//			pcur3->next = NULL;
//		*pphead1 = ret;
//	}
//	return count;
//}

int main()
{
	//先自己生成三组链表
	//第一组，[1，2，3，4，5]和[3，4，5，6，7]
	SLTNode* phead1 = NULL;
	SLTNode* phead2 = NULL;
	SLTPushBack(&phead1, 1);
	SLTPushBack(&phead1, 2);
	SLTPushBack(&phead1, 3);
	SLTPushBack(&phead1, 4);
	SLTPushBack(&phead1, 5);
	SLTPushBack(&phead2, 3);
	SLTPushBack(&phead2, 4);
	SLTPushBack(&phead2, 5);
	SLTPushBack(&phead2, 6);
	SLTPushBack(&phead2, 7);
	CommonSet(phead1, phead2, &phead1);
	SLTPrint(phead1);
	//第二组，[1，3，5，7，9]和[2，4，6，8，10]
	SLTNode* phead3 = NULL;
	SLTNode* phead4 = NULL;
	SLTPushBack(&phead3, 1);
	SLTPushBack(&phead3, 3);
	SLTPushBack(&phead3, 5);
	SLTPushBack(&phead3, 7);
	SLTPushBack(&phead3, 9);
	SLTPushBack(&phead4, 2);
	SLTPushBack(&phead4, 4);
	SLTPushBack(&phead4, 6);
	SLTPushBack(&phead4, 8);
	SLTPushBack(&phead4, 10);
	CommonSet(phead3, phead4, &phead3);
	SLTPrint(phead3);
	//第三组，[]和[3,4,5,6,7]
	SLTNode* phead5 = NULL;
	SLTNode* phead6 = NULL;
	SLTPushBack(&phead6, 3);
	SLTPushBack(&phead6, 4);
	SLTPushBack(&phead6, 5);
	SLTPushBack(&phead6, 6);
	SLTPushBack(&phead6, 7);
	CommonSet(phead5, phead6, &phead5);
	SLTPrint(phead5);
	return 0;
}